//Given an array where elements are sorted in ascending order, convert it to a h
//eight balanced BST. 
//
// For this problem, a height-balanced binary tree is defined as a binary tree i
//n which the depth of the two subtrees of every node never differ by more than 1.
// 
//
// Example: 
//
// 
//Given the sorted array: [-10,-3,0,5,9],
//
//One possible answer is: [0,-3,9,-10,null,5], which represents the following he
//ight balanced BST:
//
//      0
//     / \
//   -3   9
//   /   /
// -10  5
// 
// Related Topics 树 深度优先搜索


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun sortedArrayToBST(nums: IntArray): TreeNode? {
        return sortedArrayToBST(nums, 0 , nums.size - 1)
    }

    fun sortedArrayToBST(nums: IntArray, start:Int, end:Int): TreeNode? {
        if(start > end){
            return null
        }
        val mid = (start + end) / 2
        val root = TreeNode(nums[mid])
        root.left = sortedArrayToBST(nums, start, mid-1)
        root.right = sortedArrayToBST(nums, mid+1,end)
        return root

    }
}
//leetcode submit region end(Prohibit modification and deletion)
